package A_review.re2_16;

import binaryTree.TreeNode;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

public class BianLi {


    public  void   traverse(TreeNode  root, ArrayList<Integer> ans){
        if (root==null){
            return;
        }
        //TODO:2024/2/16  替换这个位置进行前中后序白遍历顺序的变化
        ans.add(root.val);
        traverse(root.left,ans);
        traverse(root.right,ans);
    }


    List<List<Integer>> ans;
    public  List<List<Integer>> layerTraverse(TreeNode root){
        ans=new ArrayList<>();
        if (root==null){
            return ans;
        }
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty()){
//            Integer pop = stack.pop();
            ArrayList<Integer> temp = new ArrayList<>();
            TreeNode node = stack.pop();
            temp.add(node.val);
            if (node.left!=null){
                stack.add(node.left);
            }
            if (node.right!=null){
                stack.add(node.right);
            }
            ans.add(temp);
        }
        return  ans;
    }


    public  List<Integer>  feidiguiPreOrder(TreeNode  root){
        ArrayList<Integer> ans = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
         if (root==null){
             return  ans;
         }
         stack.push(root);
         while (!stack.isEmpty()){
             TreeNode node = stack.pop();
             ans.add(node.val);
             if (node.right!=null){
                 stack.add(node.right);
             }
             if (node.left!=null){
                 stack.add(node.left);
             }
         }
        return ans;
    }


    public  List<Integer>  feidiguiPostOrder(TreeNode  root){
        ArrayList<Integer> ans = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root==null){
            return  ans;
        }
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            ans.add(node.val);
            if (node.left!=null){
                stack.add(node.left);
            }
            if (node.right!=null){
                stack.add(node.right);
            }
        }
        Collections.reverse(ans);
        return ans;
    }



    public  List<Integer>  feidiguiInOrder(TreeNode  root){
        ArrayList<Integer> ans = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root==null){
            return  ans;
        }
        TreeNode  cur=root;
        while (cur!=null||!stack.isEmpty()){
            if (cur.left!=null){
                stack.push(cur.left);
                cur=cur.left;
            }else {
                TreeNode pop = stack.pop();
                ans.add(pop.val);
                cur=cur.right;
            }
        }
        return ans;
    }




    }
